package number_operatation.leetcode.medium;

/**
 * @author bruin_du
 * @description 单词长度的最大乘积
 * @date 2022/8/2 15:12
 **/
public class OfferII005_MaxProduct {
    public int maxProduct(String[] words) {
        //方法一：暴力解法
        //使用26个int数组查找比使用库函数的indexOf快了不少
        method1(words);

        //方法二：位运算
        //既然只有小写字母,就可以利用26个比特位进行判断是否有相同字母出现
        return method2(words);
    }

    private int method1(String[] words) {
        int res = 0;
        for (int i = 0; i < words.length - 1; i++) {
            int[] index = generateIndex(words[i]);
            for (int j = i + 1; j < words.length; j++) {
                int count = 0;
                for (int k = 0; k < words[j].length(); k++) {
                    if (index[words[j].charAt(k) - 'a'] != 0) {
                        count = 0;
                        break;
                    }
                    count++;
                }
                res = Math.max(res, count * words[i].length());
            }
        }
        return res;
    }

    private int[] generateIndex(String str) {
        int[] index = new int[26];
        for (int i = 0; i < str.length(); i++) {
            index[str.charAt(i) - 'a']++;
        }
        return index;
    }

    private int method2(String[] words) {
        int length = words.length;
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            int tmp = 1;
            for (int j = 0; j < words[i].length(); j++) {
                arr[i] |= (tmp << words[i].charAt(j) - 'a');
            }
        }

        int res = 0;
        for (int i = 0; i < length - 1; i++) {
            for (int j = i + 1; j < length; j++) {
                if ((arr[i] & arr[j]) == 0) {
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }
}
